\subsection{Aggregation: Vectors}

\label{lib-vector}

\index{Vector}
{\bf Package}

\begin{verbatim}
import Vector :: * ;
\end{verbatim}

\com{Vector}
{\bf Description}


The {\te{Vector}}  package defines an abstract data type which is
a container of a specific length, holding elements of one type.  Functions which create and operate
on this type are also defined within this package.
Because it is abstract, there are no constructors available for this type
(like {\te{Cons}} and {\te{Nil}} for the {\te{List}} type).
\begin{libverbatim}
     typedef struct Vector#(type numeric vsize, type element_type); 
\end{libverbatim}

Here, the type variable \te{element\_type} represents the type of the
contents of the elements 
while the numeric type variable {\te{vsize}} represents the length of the
vector.

If the elements are in the \te{Bits} class, then the vector is as
well.  Thus a vector of these elements can be stored into Registers or
FIFOs; for example  a Register holding a vector of type \te{int}.  Note
that a vector can also store abstract types, such as a vector of \te{Rules}
or a vector of 
\te{Reg} interfaces. These are useful during static elaboration
although they have no hardware implementation.


{\bf Typeclasses}

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
\multicolumn{11}{|c|}{Type Classes for \te{Vector}}\\
\hline
\hline
&\te{Bits}&\te{Eq}&\te{Literal}&\te{Arith}&\te{Ord}&\te{Bounded}&\te{Bitwise}&\te{Bit}&\te{Bit}&\te{FShow}\\
&&&&&&&&Reduction&Extend&\\
\hline
\te{Vector}&$\surd$&$\surd$&&&&$\surd$&&&&$\surd$\\
\hline
\end{tabular}
\end{center}

\paragraph{Bits}

A vector can be turned into bits if the individual elements can be
turned into bits.  When packed and unpacked, the zeroth element of the
vector is stored in the least 
significant bits.  The size of the resulting bits is given by
$ tsize = vsize * {\tt SizeOf\#}( element\_type )$ which is specified in the
provisos.
\begin{libverbatim}
instance Bits #( Vector#(vsize, element_type), tsize)
   provisos (Bits#(element_type, sizea), 
             Mul#(vsize, sizea, tsize));
\end{libverbatim}

Vectors are zero-indexed; the first element of a vector \te{v}, is \te{v[0]}.
When vectors are packed, they are packed in order from the LSB to the MSB.

Example. Vector\#(5, Bit\#(7)) v1;

From the type, you can see that this will back into a 35-bit vector (5
elements, each with 7 bits).

MSB \begin{tabular}{|p {.5in}|p {.5 in}|p {.5 in}|p {.5 in}|p {.5 in}|}
\hline
\multicolumn{1}{|l}{34}&\multicolumn{3}{c}{bit positions}&\multicolumn{1}{r|}{0}\\
\hline
v1[4]&v1[3]&v1[2]&v1[1]&v1[0]\\ 
\hline
\end{tabular} LSB

Example. A vector with a structure:
\begin{libverbatim}
typedef struct { Bool a, UInt#(5) b} Newstruct deriving (Bits);
Vector#(3, NewStruct) v2;
\end{libverbatim} 

The structure, \te{Newstruct} packs into 6 bits.  Therefore
\te{v2} will pack into an 18-bit vector.  And its structure
would look as follows:

MSB \begin{tabular}{|p {.35 in}|p {1.1 in}|p {.35 in}|p {1.1 in}|p {.35 in}|p
{1.1 in}|}
\hline
\multicolumn{1}{|c}{17}&\multicolumn{1}{|c|}{16 -
12}&\multicolumn{1}{c}{11}&\multicolumn{1}{|c|}{10 -
6}&\multicolumn{1}{c}{5}&\multicolumn{1}{|r|}{0}\\
\hline
v2[2].a&v2[2].b&v2[1].a&v2[1].b&v2[0].a&v2[0].b\\
\hline
\multicolumn{2}{|c|}{v2[2]}&\multicolumn{2}{|c|}{v2[1]}&\multicolumn{2}{|c|}{v2[0]}\\
\hline
\end{tabular} LSB


\paragraph{Eq}

Vectors can be compared for equality if the elements can.  That is,
the operators \te{==} and \te{!=} are defined.

\paragraph{Bounded}

Vectors are bounded if the elements are.


\paragraph{FShow}

The \te{FShow} class provides the \te{fshow} function which can be
applied to a \te{Vector} and returns an associated \te{Fmt} object showing:

\begin{verbatim}
<V elem1 elem2 ...>
\end{verbatim}
where the \te{elemn} are the elements of the vector with  \te{fshow}
 applied to each element value.

\subsubsection{Creating and Generating Vectors}

The following functions are used to create new vectors, with and
without defined elements.
There are no constructors available for this abstract type
(and hence no pattern-matching is available for this type)
but the following  functions may be used to construct values of
the \te{Vector} type.

\com{newVector}
\index{newVector@\te{newVector} (\te{Vector} function)}
\index[function]{Vector!newVector}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&  \\
\te{newVector}&Generate a vector with undefined elements, typically used when
 vectors are declared.\\
&  \\
\cline{2-2}
&\begin{libverbatim}function Vector#(vsize, element_type) newVector();\end{libverbatim}
\\
\hline
\end{tabular}

\com{genVector}
\index{genVector@\te{genVector} (\te{Vector} function)}
\index[function]{Vector!genVector}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&  \\
\te{genVector}&Generate a vector containing integers 0 through n-1,
vector[0] will have value 0.\\
&  \\
\cline{2-2}
&\begin{libverbatim}function Vector#(vsize, Integer) genVector();\end{libverbatim}
\\
\hline
\end{tabular}

\com{replicate}
\index{replicate@\te{replicate} (\te{Vector} function)}
\index[function]{Vector!replicate}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&  \\
\te{replicate}&Generate a vector of elements by replicating the given argument
(c).\\
&  \\
\cline{2-2}
&\begin{libverbatim}function Vector#(vsize, element_type) replicate(element_type c);\end{libverbatim}
\\
\hline
\end{tabular}

\com{genWith}
\index{genWith@\te{genWith} (\te{Vector} function)}
\index[function]{Vector!genWith}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&  \\
\te{genWith}&Generate a vector of elements by applying the given
function to 0 through n-1.  The argument to the function is another
function which has one argument of type \te{Integer} and returns an \te{element\_type}.\\
&  \\
\cline{2-2}
&\begin{libverbatim}
function Vector#(vsize, element_type) 
         genWith(function element_type func(Integer x1));\end{libverbatim}
\\
\hline
\end{tabular}

\com{cons}
\index{cons@\te{cons} (\te{Vector} function)}
\index[function]{Vector!cons}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&  \\
\te{cons}&Adds an element to a vector creating a vector one element larger.
The new element will be at the 0th position.  This function can lead
to large compile times, so it can be an 
 inefficient way to create and populate a  vector.  Instead, 
the designer should build a vector, then set
each element to a value.  \\
&  \\
\cline{2-2}
&\begin{libverbatim}
function Vector#(vsize1, element_type)
     cons (element_type elem, Vector#(vsize, element_type) vect)
  provisos (Add#(1, vsize, vsize1));\end{libverbatim}
\\
\hline
\end{tabular}

\index{nil@\te{nil} (\te{Vector} function)}
\index[function]{Vector!nil}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&  \\
\te{nil}&Defines a  vector of size zero.\\
&  \\
\cline{2-2}
&\begin{libverbatim}function Vector#(0, element_type) nil;\end{libverbatim}
\\
\hline
\end{tabular}

\index{append@\te{append} (\te{Vector} function)}
\index[function]{Vector!append}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&  \\
\te{append}&Append two vectors containing elements of the same type,
returning the combined vector.  The resulting vector \te{result} will
contain all 
the elements of \te{vecta} followed by all the elements of
\te{vectb}.  \te{result[0]} = \te{vecta[0]},
\te{result[vsize-1]} = \te{vectb[v1size-1]}.\\
&  \\\cline{2-2}
&\begin{libverbatim}
function Vector#( vsize, element_type ) 
      append( Vector#(v0size,element_type) vecta, 
              Vector#(v1size,element_type) vectb)  
  provisos (Add#(v0size, v1size, vsize)); //vsize = v0size + v1size\end{libverbatim}               
\\
\hline
\end{tabular}

\index{concat@\te{concat} (\te{Vector} function)}
\index[function]{Vector!concat}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&  \\\te{concat}&Append (\emph{con}catenate) many vectors, that is a
vector of vectors into one vector.  \te{concat(xss)[0]}will be
\te{xss[0][0]}, provided \te{m} and \te{n} are non-zero. \\
&  \\\cline{2-2}
&\begin{libverbatim}
function Vector#(mvsize,element_type)
      concat(Vector#(m,Vector#(n,element_type)) xss)
  provisos (Mul#(m,n,mvsize));\end{libverbatim}
\\
\hline
\end{tabular}

{\bf Examples - Creating and Generating Vectors}

Create a new vector, \te{my\_vector}, of 5 elements of datatytpe
\te{Int\#(32)}, with elements which are undefined.
\begin{libverbatim}
     Vector #(5, Int#(32)) my_vector;
\end{libverbatim}

Create a new vector, \te{my\_vector}, of 5 elements of datatytpe \te{Integer} with elements 0, 1, 2, 3 and 4.
\begin{libverbatim}
     Vector #(5, Integer) my_vector = genVector;
     // my_vector is a 5 element vector {0,1,2,3,4}
\end{libverbatim}

Create a vector, my\_vector,  of five 1's.
\begin{libverbatim}
     Vector #(5,Int #(32)) my_vector = replicate (1);
     // my_vector is a 5 element vector {1,1,1,1,1}
\end{libverbatim} 

Create a vector, \te{my\_vector},  by applying the given function \te{add2} to 0
through n-1.
\begin{libverbatim}
     function Integer add2 (Integer a);
         Integer c = a + 2;
	     return(c);
     endfunction

     Vector #(5,Integer) my_vector = genWith(add2);
   
     // a is the index of the vector, 0 to n-1
     // my_vector = {2,3,4,5,6,}
\end{libverbatim}

Add an element to \te{my\_vector}, creating a bigger vector \te{my\_vector1}.
\begin{libverbatim}
     Vector#(3, Integer) my_vector = genVector();
     // my_vector = {0, 1, 2}

     let my_vector1 = cons(4, my_vector);
     // my_vector1 = {4, 0, 1, 2}
\end{libverbatim}

Append vectors, \te{my\_vector} and \te{my\_vector1}, resulting in a vector \te{my\_vector2}.
\begin{libverbatim}
     Vector#(3, Integer) my_vector = genVector();
     // my_vector = {0, 1, 2}

     Vector#(3, Integer) my_vector1 = genWith(add2);
     // my_vector1 = {2, 3, 4}

     let my_vector2 = append(my_vector, my_vector1);
     // my_vector2 = {0, 1, 2, 2, 3, 4}
\end{libverbatim}

% Obtain a vector, \te{my\_vector}, from a two dimensions vector, \te{matrix}.
% \begin{libverbatim}
%      Vector#(3, Vector#(3, Integer)) matrix;
%      for (Integer i = 0; i < 3; i = i + 1)
%      matrix[i] = genVector;

%      // matrix[0] = {0, 1, 2}
%      // matrix[1] = {3, 4, 5}
%      // matrix[2] = {6, 7, 8}

%      let my_vector = concat (matrix);
%      // my_vector = {0, 1, 2, 3, 4, 5, 6, 7, 8} 
% \end{libverbatim}

%---------------------------------------------------------------------

\subsubsection{Extracting Elements and Sub-Vectors}

These functions are used to select elements or vectors from existing
vectors, while retaining the input vector.

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{[i]}&   The square-bracket notation is available to extract an 
element from a vector or update an element within it.  Extracts or updates 
the ith element, where the first element is [0]. Index i must be of an
acceptable index type 
(e.g. \te{Integer}, \te{Bit\#(n)}, \te{Int\#(n)} or \te{UInt\#(n)}). The square-bracket 
notation for vectors can also be used with register writes.\\% (as described in section \ref{sec-registers-and-brackets}).\\
& \\ \cline{2-2}
&\begin{libverbatim}
anyVector[i];
anyVector[i] = newValue;
\end{libverbatim}
\\
\hline
\end{tabular}

\index{select@\te{select} (\te{Vector} function)}
\index[function]{Vector!select}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\
\te{select}&The select function is another form of the subscript
notation ([i]), mainly provided for backwards-compatibility. The 
select function is also useful as an argument to higher-order
functions. The subscript notation is generally recommended because 
it will report a more useful position for any selection errors.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function element_type 
      select(Vector#(vsize,element_type) vect, idx_type index);\end{libverbatim}
\\
\hline
\end{tabular}

\index{update@\te{update} (\te{Vector} function)}
\index[function]{Vector!update}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\
\te{update}&Update an element in a vector returning a new vector with
one element changed/updated. This function does not change the given vector.
This is another form of the subscript notation (see above), mainly 
provided for backwards compatibility. The update function may also be 
useful as an argument to a higher-order function. The subscript notation 
is generally recommended because it will report a more useful position 
for any update errors.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize, element_type) 
      update(Vector#(vsize, element_type) vectIn,
             idx_type index, 
             element_type newElem);\end{libverbatim}
\\
\hline
\end{tabular}

\index{head@\te{head} (\te{Vector} function)}
\index[function]{Vector!head}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{head}&Extract the zeroth (head) element of a
vector. The vector must have at least one element. \\
& \\ \cline{2-2}
&\begin{libverbatim}
function element_type 
      head (Vector#(vsize, element_type) vect)
  provisos(Add#(1,xxx,vxize)); // vsize >= 1
\end{libverbatim}
\\
\hline
\end{tabular}

\index{last@\te{last} (\te{Vector} function)}
\index[function]{Vector!last}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{last}&Extract the highest (tail) element of a vector.  The
vector must have at least one element.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function element_type 
      last (Vector#(vsize, element_type) vect)
  provisos(Add#(1,xxx,vxize)); // vsize >= 1
\end{libverbatim}
\\
\hline
\end{tabular}

\index{tail@\te{tail} (\te{Vector} function)}
\index[function]{Vector!tail}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{tail}&Remove the head element of a vector leaving its tail in
a smaller vector.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,element_type) 
      tail (Vector#(vsize1, element_type) xs)
  provisos (Add#(1, vsize, vsize1));\end{libverbatim}
\\
\hline
\end{tabular}

\index{init@\te{init} (\te{Vector} function)}
\index[function]{Vector!init}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{init}&Remove the last element of a vector leaving its initial
part in a smaller vector.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,element_type) 
      init (Vector#(vsize1, element_type) xs)
  provisos (Add#(1, vsize, vsize1));\end{libverbatim}
\\
\hline
\end{tabular}

\index{take@\te{take} (\te{Vector} function)}
\index[function]{Vector!take}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{take}&Take a number of elements from a vector starting from
index 0.  The number of elements to take is indicated by the type of
the context where this is called, and is not specified as an argument
to the function. \\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vxize2,element_type) 
      take (Vector#(vsize,element_type) vect)
  provisos (Add#(vsize2,xxx,vsize)); // vsize2 <= vsize.\end{libverbatim}
\\
\hline
\end{tabular}

\index{drop@\te{drop} (\te{Vector} function)}
\index[function]{Vector!drop}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{drop} \te{takeTail}&Drop  a number of elements from the vector starting at
the 0th position.  The elements in the result vector will
be in the same order as the input vector.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vxize2,element_type) 
      drop (Vector#(vsize,element_type) vect)
  provisos (Add#(vsize2,xxx,vsize)); // vsize2 <= vsize.

function Vector#(vxize2,element_type) 
      takeTail (Vector#(vsize,element_type) vect)
  provisos (Add#(vsize2,xxx,vsize)); // vsize2 <= vsize.\end{libverbatim}
\\
\hline
\end{tabular}


% \begin{tabular}{|p{.7 in}|p{4.9 in}|}
% \hline
% & \\ \te{takeTail}&Take a number of elements from the tail by dropping
% elements at the 0th position.  The elements in the result vector will
% be in the same order as the input vector.\\
% & \\ \cline{2-2}
% &\begin{libverbatim}
% function Vector#(vxize2,element_type) 
%       takeTail (Vector#(vsize,element_type) vect)
%   provisos (Add#(vsize2,xxx,vsize)); // vsize2 <= vsize.\end{libverbatim}
% \\
% \hline
% \end{tabular}

\index{takeAt@\te{takeAt} (\te{Vector} function)}
\index[function]{Vector!takeAt}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{takeAt}&Take a number of elements starting at \te{startPos}.
\te{startPos} must be a compile-time constant.  If the \te{startPos}
plus the output vector size extend beyond the  end of the input vector,
an error will be returned.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize2,element_type) 
       takeAt (Integer startPos, Vector#(vsize,element_type) vect)
  provisos (Add#(vsize2,xxx,vsize)); // vsize2 <= vsize
\end{libverbatim}
\\
\hline
\hline
\end{tabular}

{\bf Examples - Extracting Elements and Sub-Vectors}

Extract the element from a vector, \te{my\_vector}, at the position of index.
\begin{libverbatim}
     // my_vector is a vector of elements {6,7,8,9,10,11}
     // index = 3
     // select or [ ] will generate a MUX
    
     newvalue = select (my_vector, index);
     newvalue = myvalue[index];
     // newvalue = 9
\end{libverbatim}


Update the element of a vector, \te{my\_vector}, at the position of index.
\begin{libverbatim}
     // my_vector is a vector of elements {6,7,8,9,10,11}
     // index = 3

     my_vector = update (my_vector, index, 0);
     my_vector[index] = 0;
     // my_vector = {6,7,8,0,10,11}
\end{libverbatim}

Extract the zeroth element of the vector \te{my\_vector}.
\begin{libverbatim}
     // my_vector is a vector of elements {6,7,8,9,10,11}

     newvalue = head(my_vector);
     // newvalue = 6
\end{libverbatim} 

Extract the last element of the vector \te{my\_vector}.
\begin{libverbatim}
     // my_vector is a vector of elements {6,7,8,9,10,11}

     newvalue = last(my_vector);
     // newvalue = 11 
\end{libverbatim}

Create a vector, \te{my\_vector2},  of size 4 by removing the head (zeroth)
element of the vector \te{my\_vector1}.
\begin{libverbatim}
     // my_vector1 is a vector with 5 elements {0,1,2,3,4}

     Vector #(4, Int#(32)) my_vector2 = tail (my_vector1);
     // my_vector2 is a vector of 4 elements {1,2,3,4}
\end{libverbatim}

Create a vector, \te{my\_vector2},  of size 4 by removing the tail (last)
element of the vector \te{my\_vector1}.
\begin{libverbatim}
     // my_vector1 is a vector with 5 elements {0,1,2,3,4}

     Vector #(4, Int#(32)) my_vector2 = init (my_vector1);
     // my_vector2 is a vector of 4 elements {0,1,2,3}
\end{libverbatim}

Create a 2 element vector, \te{my\_vector2},  by taking the first two
elements of the vector \te{my\_vector1}.
\begin{libverbatim}
     // my_vector1 is vector with 5 elements {0,1,2,3,4}

     Vector #(2, Int#(4)) my_vector2 = take (my_vector1);
     // my_vector2 is a 2 element vector {0,1}
\end{libverbatim}

Create a 3 element vector, \te{my\_vector2},  by taking the last 3 
elements of  vector, \te{my\_vector1}.
using \te{takeTail}
\begin{libverbatim}
     // my_vector1 is Vector with 5 elements {0,1,2,3,4}

     Vector #(3,Int #(4)) my_vector2 = takeTail (my_vector1);
     // my_vector2 is a 3 element vector {2,3,4}
\end{libverbatim}


Create a 3 element vector, \te{my\_vector2},  by taking the 1st - 3rd
elements of  vector, \te{my\_vector1}.
using \te{takeAt}
\begin{libverbatim}
     // my_vector1 is Vector with 5 elements {0,1,2,3,4}

     Vector #(3,Int #(4)) my_vector2 = takeAt (1, my_vector1);
     // my_vector2 is a 3 element vector {1,2,3}
\end{libverbatim}


%-----------------------------------------------------------------

\subsubsection{Vector to Vector Functions}

The following functions generate a new vector by changing the position
of elements within the vector.

\index{rotate@\te{rotate} (\te{Vector} function)}
\index[function]{Vector!rotate}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{rotate} & Move the zeroth element to the highest and shift each
element lower by one.  For example, the element at index \te{n} moves
to index \te{n-1}.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,element_type) 
      rotate (Vector#(vsize,element_type) vect);
\end{libverbatim}
\\
\hline
\end{tabular}

\index{rotateR@\te{rotateR} (\te{Vector} function)}
\index[function]{Vector!rotateR}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{rotateR} & Move last element to the zeroth element and shift each
element up by one. For example, the element at index \te{n} moves to
index \te{n+1}.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,element_type)  
      rotateR (Vector#(vsize,element_type) vect);
\end{libverbatim}
\\
\hline
\end{tabular}

\index{rotateBy@\te{rotateBy} (\te{Vector} function)}
\index[function]{Vector!rotateBy}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{rotateBy} & Shift each element  \te{n}
places.  The last \te{n} elements are moved to the beginning,
the element at index \te{0} moves to index \te{n}, index \te{1} to index
\te{n+1}, etc.  \\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize, element_type)  
      rotateBy (Vector#(vsize,element_type) vect, UInt#(log(v)) n)
  provisos (Log#(vsize, logv);
\end{libverbatim}
\\
\hline
\end{tabular}

\index{shiftInAt0@\te{shiftInAt0} (\te{Vector} function)}
\index[function]{Vector!shiftInAt0}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{shiftInAt0} & Shift a new element into the vector at index 0,
bumping the index of  all other element  up by one.  The highest element is dropped.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,element_type) 
      shiftInAt0 (Vector#(vsize,element_type) vect, 
                  element_type newElement);
\end{libverbatim}
\\
\hline
\end{tabular}

\index{shiftInAtN@\te{shiftInAtN} (\te{Vector} function)}
\index[function]{Vector!shiftInAtN}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{shiftInAtN} & Shift a new element into the vector at index n,
bumping the index of all other elements down by one.  The 0th element is
dropped. \\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,element_type) 
      shiftInAtN (Vector#(vsize,element_type) vect, 
                  element_type newElement);
\end{libverbatim}
\\
\hline
\end{tabular}

\index{shiftOutFrom0@\te{shiftOutFrom0} (\te{Vector} function)}
\index[function]{Vector!shiftOutFrom0}

\begin{tabular}{|p{.9 in}|p{4.7 in}|}
\hline
&\\ \te{shiftOutFrom0} & Shifts out \te{amount} number of elements from the 
vector starting at index 0, 
bumping the index of  all remaining elements  down by \te{amount}.  The
shifted elements are replaced with the  value \te{default}.  This
function is similar to a \verb|>>| bit operation.
\te{amt\_type} must be of an acceptable index type 
(\te{Integer}, \te{Bit\#(n)}, \te{Int\#(n)} or \te{UInt\#(n)}). \\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,element_type) 
      shiftOutFrom0 (element_type default, 
                     Vector#(vsize,element_type) vect, 
                     amt_type amount);
\end{libverbatim}
\\
\hline
\end{tabular}

\index{shiftOutFromN@\te{shiftOutFromN} (\te{Vector} function)}
\index[function]{Vector!shiftOutFromN}
\begin{tabular}{|p{.9 in}|p{4.7 in}|}
\hline
&\\ \te{shiftOutFromN} &  Shifts out  \te{amount} number of elements
from the vector starting at index \te{vsize-1}
bumping the index of  remaining elements  up by \te{amount}.  The
shifted elements are replaced with the  value \te{default}.  This
function is similar to a \verb|<<| bit operation.
\te{amt\_type} must be of an acceptable index type 
(\te{Integer}, \te{Bit\#(n)}, \te{Int\#(n)} or \te{UInt\#(n)}). \\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,element_type) 
      shiftOutFromN (element_type default, 
                     Vector#(vsize,element_type) vect, 
                     amt_type amount);
\end{libverbatim}
\\
\hline
\end{tabular}

\index{reverse@\te{reverse} (\te{Vector} function)}
\index[function]{Vector!reverse}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{reverse} & Reverse element order\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,element_type) 
      reverse(Vector#(vsize,element_type) vect);
\end{libverbatim}
\\
\hline
\end{tabular}

\index{transpose@\te{transpose} (\te{Vector} function)}
\index[function]{Vector!transpose}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{transpose} &Matrix transposition of a vector of vectors.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(m,Vector#(n,element_type)) 
      transpose ( Vector#(n,Vector#(m,element_type)) matrix );
\end{libverbatim}
\\
\hline
\end{tabular}
\index{transposeLN@\te{transposeLN} (\te{Vector} function)}
\index[function]{Vector!transposeLN}

\begin{tabular}{|p{.8 in}|p{4.8 in}|}
\hline
&\\ \te{transposeLN} & Matrix transposition of a vector of Lists.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize, List#(element_type)) 
      transposeLN( List#(Vector#(vsize, element_type)) lvs );
\end{libverbatim}
\\
\hline
\hline
\end{tabular}

{\bf Examples - Vector to Vector Functions}

Create a vector by moving the last element to the first, then shifting
each element to the right.

\begin{libverbatim}
     // my_vector1 is a vector of elements with values {1,2,3,4,5}
    
     my_vector2 = rotateR (my_vector1);
     // my_vector2 is a vector of elements with values {5,1,2,3,4}
\end{libverbatim}


Create a vector which is the input vector rotated by 2 places.
\begin{libverbatim}
     // my_vector1 is a vector of elements {1,2,3,4,5}
     
     my_vector2 = rotateBy {my_vector1, 2};
     // my_vector2 = {4,5,1,2,3}  
\end{libverbatim}


Create a vector which shifts out 3 elements starting from 0, replacing
them with the value F

\begin{libverbatim}
     // my_vector1 is a vector of elements {5,4,3,2,1,0}
     
     my_vector2 = shiftOutFrom0 (F, my_vector1, 3);
     // my_vector2 is a vector of elements {F,F,F,5,4,3}
\end{libverbatim}


Create a vector which shifts out 3 elements starting from n-1, replacing
them with the value F

\begin{libverbatim}
     // my_vector1 is a vector of elements {5,4,3,2,1,0}
     
     my_vector2 = shiftOutFromN (F, my_vector1, 3);
     // my_vector2 is a vector of elements {2,1,0,F,F,F}
\end{libverbatim}



Create a vector which is the reverse of the input vector.
\begin{libverbatim}
     // my_vector1 is a vector of elements {1,2,3,4,5}
     
     my_vector2 = reverse (my_vector1);
     // my_vector2 is a vector of elements {5,4,3,2,1}
\end{libverbatim}

Use transpose to create a new vector.
\begin{libverbatim}
     // my_vector1 is a Vector#(3, Vector#(5, Int#(8)))
     // the result, my_vector2, is a Vector #(5,Vector#(3,Int #(8))) 
     
     // my_vector1 has the values:
     // {{0,1,2,3,4},{5,6,7,8,9},{10,11,12,13,14}}
     
     my_vector2 = transpose(my_vector1);
     // my_vector2 has the values:
     // {{0,5,10},{1,6,11},{2,7,12},{3,8,13},{4,9,14}} 
\end{libverbatim}


%------------------------------------------------------------------

\subsubsection{Tests on Vectors}
 
The following functions are used to test vectors.  The first set of 
functions are Boolean functions, i.e. they return
\te{True} or \te{False} values. 

\index{elem@\te{elem} (\te{Vector} function)}
\index[function]{Vector!elem}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{elem} &Check if a value is an element of a vector.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Bool elem (element_type x, 
                    Vector#(vsize,element_type) vect )
  provisos (Eq#(element_type));
\end{libverbatim}
\\
\hline
\end{tabular}

\index{all@\te{all} (\te{Vector} function)}
\index[function]{Vector!all}
\index[function]{Vector!any}
\index{any@\te{any} (\te{Vector} function)}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{any}&Test if a predicate holds for any element of a vector.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Bool any(function Bool pred(element_type x1), 
                  Vector#(vsize,element_type) vect );
\end{libverbatim}
\\
\hline
\end{tabular}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{all}&Test if a predicate holds for all elements of a vector.\\
&\\ \cline{2-2}
&\begin{libverbatim}
function Bool all(function Bool pred(element_type x1), 
                  Vector#(vsize,element_type) vect );
\end{libverbatim}
\\
\hline
\hline
\end{tabular}

\index{and@\te{and} (\te{Vector} function)}
\index[function]{Vector!and}
\index{or@\te{or} (\te{Vector} function)}
\index[function]{Vector!or}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{or}&Combine all elements in a vector of Booleans with a
logical or.  Returns True  if any elements in the Vector are True.\\
&\\ \cline{2-2}
&\begin{libverbatim}
function Bool or (Vector#(vsize, Bool) vect );
\end{libverbatim}
\\
\hline
\hline
\end{tabular}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{and}&Combine all elements in a vector of Booleans with a
logical and.  Returns True  if all elements in the Vector are True.\\
&\\ \cline{2-2}
&\begin{libverbatim}
function Bool and (Vector#(vsize, Bool) vect );
\end{libverbatim}
\\
\hline
\hline
\end{tabular}


The following two functions return the number of elements in the
vector which match a condition.

\index{countElem@\te{countElem} (\te{Vector} function)}
\index[function]{Vector!countElem}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{countElem}&Returns the number of elements in the vector which
are equal to a given value.  The return value is in the range of 0 to vsize.\\
&\\ \cline{2-2}
&\begin{libverbatim}
function UInt#(logv1) countElem (element_type x, 
                                 Vector#(vsize, element_type) vect)
  provisos (Eq#(element_type), Add#(vsize, 1, vsize1), 
            Log#(vsize1, logv1));
\end{libverbatim}
\\
\hline
\hline
\end{tabular}

\index{countIf@\te{countIf} (\te{Vector} function)}
\index[function]{Vector!countIf}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{countIf}&Returns the number of elements in the vector which
satisfy a given predicate function.  The return value is in the range of 0 to vsize.\\
&\\ \cline{2-2}
&\begin{libverbatim}
function UInt#(logv1) countIf (function Bool pred(element_type x1)
                               Vector#(vsize, element_type) vect)
  provisos (Add#(vsize, 1, vsize1), Log#(vsize1, logv1));
\end{libverbatim}
\\
\hline
\hline
\end{tabular}

\index{find@\te{find} (\te{Vector} function)}
\index[function]{Vector!find}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{find}&Returns the first element that satisfies the predicate
or \te{Nothing} if there is none.\\
&\\ \cline{2-2}
&\begin{libverbatim}
function Maybe#(element_type)
      find (function Bool pred(element_type), 
            Vector#(vsize, element_type) vect);
\end{libverbatim}
\\
\hline
\hline
\end{tabular}

The following two functions return the index of an element.

\index{findElem@\te{findElem} (\te{Vector} function)}
\index[function]{Vector!findElem}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{findElem}&Returns the index of the first element in the vector which
equals a given value.   Returns an \te{Invalid} if not found or
\te{Valid} with a value of 0 to vsize-1 if found.\\
&\\ \cline{2-2}
&\begin{libverbatim}
function Maybe#(UInt#(logv)) findElem (element_type x, 
                             Vector#(vsize, element_type) vect)
  provisos (Eq#(element_type), Add#(xx1, 1, vsize),  
            Log#(vsize, logv));
\end{libverbatim}
\\
\hline
\hline
\end{tabular}

\index{findIndex@\te{findIndex} (\te{Vector} function)}
\index[function]{Vector!findIndex}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{findIndex}&Returns the index of the first element in the vector which
satisfies a given predicate.  Returns an \te{Invalid} if not found or
\te{Valid} with a value of 0 to vsize-1 if found.\\
&\\ \cline{2-2}
&\begin{libverbatim}
function Maybe#(UInt#(logv)) findIndex 
                          (function Bool pred(element_type x1)
                           Vector#(vsize, element_type) vect)
  provisos (Add#(xx1,1,vsize), Log#(vsize, logv));
\end{libverbatim}
\\
\hline
\hline
\end{tabular}



{\bf Examples -Tests on Vectors}

Test that all elements of the vector \te{my\_vector1} are positive integers.
\begin{libverbatim}
     function Bool isPositive (Int #(32) a);
          return (a > 0)
     endfunction

     // function isPositive checks that "a" is a  positive integer
     // if my_vector1 has n elements, n instances of the predicate
     // function isPositive will be generated.

     if (all(isPositive, my_vector1))
        $display ("Vector contains all negative values");
\end{libverbatim}

Test if any elements in the vector are positive integers.
\begin{libverbatim}
     // function isPositive checks that "a" is a  positive integer
     // if my_vector1 has n elements, n instances of the predicate
     // function isPositive will be generated.     

     if (any(isPositive, my_vector1)) 
        $display ("Vector contains some negative values");
\end{libverbatim}

Check if the integer 5 is in \te{my\_vector}.
\begin{libverbatim}
     // if my_vector contains n elements, elem will generate n copies
     // of the eq test
     if (elem(5,my_vector))
        $display ("Vector contains the integer 5");
\end{libverbatim}

Count the number of elements which match the integer provided.
\begin{libverbatim}
     // my_vector1 is a vector of {1,2,1,4,3}
     x = countElem ( 1, my_vector1);
     // x = 2
     y = countElem (4, my_vector1);
     // y = 1
\end{libverbatim}

Find the index of an element which equals a predicate.
\begin{libverbatim}
     let f = findIndex ( beIsGreaterThan( 3 ) , my_vector );
      if ( f matches tagged Valid .indx )
         begin
            printBE ( my_vector[indx] ) ;
            $display ("Found data > 3 at index %d ", indx ) ;
      else
         begin
            $display ( "Did not find data > 3" ) ;
         end
\end{libverbatim}


%----------------------------------------------------------------

\subsubsection{Bit-Vector Functions}

The following functions operate on bit-vectors.

%rotateBitsBy :: (Log n lgn, Add xxx 1 n) => Bit n -> UInt lgn ->  Bit n
\index{rotateBitsBy@\te{rotateBitsBy} (\te{bit-vector} function)}
\index[function]{Vector!rotateBitsBy}
\begin{tabular}{|p{.9 in}|p{4.7 in}|}
\hline
&\\ \te{rotateBitsBy} & Shift each bit to a higher index by \te{n}
places.  The last \te{n} bits are moved to the begininng and
the bit at index \te{(0)} moves to index \te{(n)}.  \\
& \\ \cline{2-2}
&\begin{libverbatim}
function Bit#(n) rotateBitsBy (Bit#(n) bvect, UInt#(logn) n)
  provisos (Log#(n,logn), Add#(1,xxx,n));
\end{libverbatim}
\\
\hline
\end{tabular}


\index{countOnesAlt@\te{countOnesAlt} (\te{bit-vector} function)}
\index[function]{Vector!countOnesAlt}
\begin{tabular}{|p{.9 in}|p{4.7 in}|}
\hline
&\\ \te{countOnesAlt} & Returns the number of elements equal to 1 in a
bit-vector. (This function differs slightly from the Prelude version
of countOnes and has fewer provisos.)\\
& \\ \cline{2-2}
&\begin{libverbatim}
function UInt#(logn1) countOnesAlt (Bit#(n) bvect)
  provisos (Add#(1,n,n1), Log#(n1,logn1));
\end{libverbatim}
\\
\hline
\end{tabular}


% \index{countLeadingZeros@\te{countLeadingZeros} (\te{bit-vector}function)}
% \index[function]{Vector!countLeadingZeros}
% \begin{tabular}{|p{1.2 in}|p{4.4 in}|}
% \hline
% &\\ \te{countLeadingZeros} & Returns the number of leading zeros in a bit-vector.\\
% & \\ \cline{2-2}
% &\begin{libverbatim}
% function UInt#(logn1) countLeadingZeros (Bit#(n) bvect)
%   provisos (Add#(1,n,n1), Log#(n1,logn1), 
%             Log#(n,logn), Add#(logn,xxx,logn1));
% \end{libverbatim}
% \\
% \hline
% \end{tabular}

%------------------------------------------------------------------
\subsubsection{Functions on Vectors of Registers}

\index{readVReg@\te{readVReg} (\te{Vector} function)}
\index[function]{Vector!readVReg}


\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{readVReg}&Returns the values from reading a vector of
registers (interfaces).\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(n,a) readVReg ( Vector#(n, Reg#(a)) vrin) ;
\end{libverbatim}
\\
\hline
\end{tabular}

\index{writeVReg@\te{writeVReg} (\te{Vector} function)}
\index[function]{Vector!writeVReg}


\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{writeVReg}&Returns an Action which is the write of all
registers in \te{vr} with the data from \te{vdin}.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Action writeVReg ( Vector#(n, Reg#(a)) vr, 
                            Vector#(n,a) vdin) ;
\end{libverbatim}
\\
\hline
\end{tabular}



%------------------------------------------------------------------

\subsubsection{Combining Vectors with Zip}
   
The family of \te{zip} functions takes two or more vectors and
combines them into one vector of \te{Tuples}.   Several
variations are provided for different resulting \te{Tuple}s, as
well as support for mis-matched vector sizes. 
% Tuples are described in Section \ref{sec-tuple-type}.
  

\index{zip@\te{zip} (\te{Vector} function)}
\index[function]{Vector!zip}


\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{zip}&Combine two vectors into a vector of Tuples.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,Tuple2 #(a_type, b_type))
      zip( Vector#(vsize, a_type) vecta, 
           Vector#(vsize, b_type) vectb);\end{libverbatim}
\\
\hline
\end{tabular}

\index{zip3@\te{zip3} (\te{Vector} function)}
\index[function]{Vector!zip3}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{zip3}&Combine three vectors into a vector of Tuple3.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,Tuple3 #(a_type, b_type, c_type))
      zip3( Vector#(vsize, a_type) vecta, 
            Vector#(vsize, b_type) vectb,
            Vector#(vsize, c_type) vectc);\end{libverbatim}
\\
\hline
\end{tabular}

\index{zip4@\te{zip4} (\te{Vector} function)}
\index[function]{Vector!zip4}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{zip4}&Combine four vectors into a vector of Tuple4.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,Tuple4 #(a_type, b_type, c_type, d_type))
      zip4( Vector#(vsize, a_type) vecta, 
            Vector#(vsize, b_type) vectb,
            Vector#(vsize, c_type) vectc,
            Vector#(vsize, d_type) vectd);\end{libverbatim}
\\
\hline
\end{tabular}

\index{zipAny@\te{zipAny} (\te{Vector} function)}
\index[function]{Vector!zipAny}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{zipAny}&Combine two vectors into one vector of pairs
(2-tuples); result is as long as the smaller vector.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,Tuple2 #(a_type, b_type))
      zipAny(Vector#(m,a_type) vect1, 
             Vector#(n,b_type) vect2);
  provisos (Max#(m,vsize,m), Max#(n, vsize, n));\end{libverbatim}
\\
\hline
\end{tabular}

\index{unzip@\te{unzip} (\te{Vector} function)}
\index[function]{Vector!unzip}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{unzip}&Separate a vector of pairs (i.e. a \te{Tuple2\#(a,b))} into a pair of two vectors.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Tuple2#(Vector#(vsize,a_type), Vector#(vsize, b_type))
      unzip(Vector#(vsize,Tuple2 #(a_type, b_type)) vectab);\end{libverbatim}
\\
\hline
\hline
\end{tabular}




{\bf Examples - Combining Vectors with Zip}

Combine two vectors into a vector of Tuples.
\begin{libverbatim}
     // my_vector1 is a vector of elements {0,1,2,3,4}
     // my_vector2 is a vector of elements {5,6,7,8,9}
    
     my_vector3 = zip(my_vector1, my_vector2);
     // my_vector3 is a vector of Tuples {(0,5),(1,6),(2,7),(3,8),(4,9)}
\end{libverbatim}

Separate a vector of pairs into a Tuple of two vectors.
\begin{libverbatim}
     // my_vector3 is a vector of pairs {(0,5),(1,6),(2,7),(3,8),(4,9)}

     Tuple2#(Vector #(5,Int #(5)),Vector #(5,Int #(5))) my_vector4 =
                                                    unzip(my_vector3);
     // my_vector4 is ({0,1,2,3,4},{5,6,7,8,9})
\end{libverbatim}

% ----------------------------------------------------------------

\subsubsection{Mapping Functions over Vectors}
\label{lib-vector-map}

A function can be applied to all elements of a vector, using
high-order functions such as {\tt map}.  These functions take as
an argument a function, which is applied to the elements
of the vector.  

\index{map@\te{map} (\te{Vector} function)}
\index[function]{Vector!map}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{map}&Map a function over a vector, returning a new vector of results.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,b_type) 
      map (function b_type func(a_type x),
           Vector#(vsize, a_type) vect);\end{libverbatim}
\\
\hline
\end{tabular}


{\bf Example - Mapping Functions over Vectors}

Consider the following code example which applies
the {\tt extend} function to each element of \te{avector} into a
new vector, \te{resultvector}.  
\begin{libverbatim}
      Vector#(13,Bit#(5))   avector;
      Vector#(13,Bit#(10))  resultvector;
      ...
      resultvector = map( extend, avector ) ;
\end{libverbatim}
This is equivalent to saying:
\begin{libverbatim}
      for (Integer i=0; i<13; i=i+1)
          resultvector[i] = extend(avector[i]); 
\end{libverbatim}


Map a negate function over a Vector
\begin{libverbatim}
     // my_vector1 is a vector of 5 elements {0,1,2,3,4}
     // negate is a function which makes each element negative
     
     Vector #(5,Int #(32)) my_vector2 = map (negate, my_vector1);

     // my_vector2 is a vector of 5 elements {0,-1,-2,-3,-4}
\end{libverbatim}

%-------------------------------------------------------------

\subsubsection{ZipWith Functions}

The zipWith functions combine two or more vectors with a function and
generate a new vector.  These functions combine features of map and
zip functions.

\index{zipWith@\te{zipWith} (\te{Vector} function)}
\index[function]{Vector!zipWith}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{zipWith}&Combine two vectors with a function.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,c_type)
         zipWith (function c_type func(a_type x, b_type y), 
                  Vector#(vsize,a_type) vecta, 
                  Vector#(vsize,b_type) vectb );
\end{libverbatim}
\\
\hline
\end{tabular}



\index[function]{Vector!zipWithAny}
\index{zipWithAny@\te{zipWithAny} (\te{Vector} function)}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{zipWithAny}&Combine two vectors with a function; result is as
long as the smaller vector.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,c_type) 
         zipWithAny (function c_type func(a_type x, b_type y), 
                      Vector#(m,a_type) vecta, 
                      Vector#(n,b_type) vectb )
  provisos (Max#(n, vsize, n), Max#(m, vsize, m));
\end{libverbatim}
\\
\hline
\end{tabular}

\index{zipWith3@\te{zipWith3} (\te{Vector} function)}
\index[function]{Vector!zipWith3}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{zipWith3}&Combine three vectors with a function.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,d_type) 
        zipWith3(function d_type func(a_type x, b_type y, c_type z), 
                 Vector#(vsize,a_type) vecta, 
                 Vector#(vsize,b_type) vectb, 
                 Vector#(vsize,c_type) vectc );
\end{libverbatim}
\\
\hline
\end{tabular}


\index{zipWithAny3@\te{zipWithAny3} (\te{Vector} function)}
\index[function]{Vector!zipWithAny3}
\begin{tabular}{|p{.8 in}|p{4.8 in}|}
\hline
&\\ \te{zipWithAny3}&Combine three vectors with a function; result is
as long as the smallest vector.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,c_type) 
   zipWithAny3(function d_type func(a_type x, b_type y, c_type z), 
               Vector#(m,a_type) vecta, 
               Vector#(n,b_type) vectb, 
               Vector#(o,c_type) vectc )
provisos (Max#(n, vsize, n), Max#(m, vsize, m), Max#(o, vsize, o));
\end{libverbatim}
\\
\hline
\hline
\end{tabular}

{\bf Examples - ZipWith}

Create a vector by applying a function over the elements of 3 vectors.
\begin{libverbatim}
     // the function add3 adds 3 values
     function Int#(n) add3 (Int #(n) a,Int #(n) b,Int #(n) c);
         Int#(n) d = a + b +c ;
         return d;
     endfunction
     
     // Create the vector my_vector4 by adding the ith element of each of
     // 3 vectors (my_vector1, my_vector2, my_vector3) to generate the ith
     // element of my_vector4. 

     // my_vector1 = {0,1,2,3,4}
     // my_vector2 = {5,6,7,8,9}
     // my_vector3 = {10,11,12,13,14}

     Vector #(5,Int #(8)) my_vector4 = zipWith3(add3, my_vector1, my_vector2, my_vector3);
     // creates 5 instances of the add3 function in hardware.
     // my_vector4 = {15,18,21,24,27}

     // This is equivalent to saying:
        for (Integer i=0; i<5; i=i+1)
           my_vector4[i] = my_vector1[i] + my_vector2[i] + my_vector3[i];
\end{libverbatim}



%-------------------------------------------------------------

\subsubsection{Fold Functions}

The \te{fold} family of functions reduces a vector to a single result
by  applying a function over all its elements. That is, given a
vector of {\tt element\_type}, $V_0, V_1, V_2, ..., V_{n-1}$, a seed of
type {\tt b\_type}, and a function {\tt func}, the reduction for
\te{foldr} is given by
\[ func( V_0, func(V_{1},  ... , func ( V_{n-2} , func( V_{n-1}, seed) ))) ; \] 
Note that \te{foldr} start processing from  the
highest index position to the lowest, while \te{foldl} starts
from the lowest index (zero), i.e. \te{foldl} is:
\[ func( ... ( func( func(seed, V_0), V_1), ... )  V_{n-1} ) \]

\index{foldr@\te{foldr} (\te{Vector} function)}
\index[function]{Vector!foldr}


\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{foldr}&Reduce a vector by applying a function over all its
elements.  Start processing from  the highest index to the lowest.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function b_type foldr(function b_type func(a_type x, b_type y), 
                      b_type seed, Vector#(vsize,a_type) vect);
\end{libverbatim}
\\
\hline
\end{tabular}


\index{foldl@\te{foldl} (\te{Vector} function)}
\index[function]{Vector!foldl}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{foldl}&Reduce a vector by applying a function over all its
elements.  Start processing from the lowest index (zero).\\
& \\ \cline{2-2}
&\begin{libverbatim}
function b_type foldl (function b_type func(b_type y, a_type x), 
                       b_type seed, Vector#(vsize,a_type) vect);
\end{libverbatim}
\\
\hline
\end{tabular}

The functions \te{foldr1} and \te{foldl1} use the first element as the
seed.  This means they  only work on vectors of at least one element.
Since the result type will be the same as the element type, there is
no \te{b\_type} as there is in the \te{foldr} and \te{foldl}
functions.  

\index{foldr1@\te{foldr1} (\te{Vector} function)}
\index[function]{Vector!foldr1}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{foldr1}&\te{foldr} function for a non-zero sized vector,
using element $V_{n-1}$ as a seed.
Vector must have at least 1 element.  If there is only one element, it
is returned.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function element_type foldr1(
         function element_type func(element_type x, element_type y),
         Vector#(vsize,element_type) vect)
  provisos (Add#(1, xxx, vsize));  
\end{libverbatim}
\\
\hline
\end{tabular}


\index{foldl1@\te{foldl1} (\te{Vector} function)}
\index[function]{Vector!foldl1}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{foldl1}&\te{foldl} function for a non-zero sized vector,
using element $V_0 $as a seed.
Vector must have at least 1 element. If there is only one element, it
is returned.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function element_type foldl1 (
         function element_type func(element_type y, element_type x), 
         Vector#(vsize,element_type) vect)
  provisos (Add#(1, xxx, vsize));  
\end{libverbatim}
\\
\hline
\end{tabular}

The \te{fold} function also operates over a non-empty vector, but
processing is accomplished in a binary tree-like structure.  Hence the
depth or delay through the resulting function will be $O(log_2( vsize
) $ rather than $O( vsize ) $.

\index{fold@\te{fold} (\te{Vector} function)}
\index[function]{Vector!fold}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{fold}&Reduce a vector by applying a function over all its
elements, using a binary tree-like structure.  The function returns
the same type as the arguments. \\ 
& \\ \cline{2-2}
&\begin{libverbatim}
function element_type fold (
         function element_type func(element_type y, element_type x), 
         Vector#(vsize,element_type) vect )
  provisos (Add#(1, xxx, vsize)); 
\end{libverbatim}
\\
\hline
\end{tabular}

\index{mapPairs@\te{mapPairs} (\te{Vector} function)}
\index[function]{Vector!mapPairs}
\begin{tabular}{|p{.8 in}|p{4.8 in}|}
\hline
&\\ \te{mapPairs} &Map a function over a vector consuming two elements at a time.
Any straggling element is processed by the second function.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize2,b_type) 
         mapPairs (
            function b_type func1(a_type x, a_type y), 
            function b_type func2(a_type x), 
            Vector#(vsize,a_type) vect )
  provisos (Div#(vsize, 2, vsize2));
\end{libverbatim}
\\
\hline
\end{tabular}


\index{joinActions@\te{joinActions} (\te{Vector} function)}
\index[function]{Vector!joinActions}
\begin{tabular}{|p{.8 in}|p{4.8 in}|}
\hline
&\\ \te{joinActions}&Join a number of actions together.
\te{joinActions} is used for static elaboration only, no hardware is generated.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Action joinActions (Vector#(vsize,Action) vactions);
\end{libverbatim}
\\
\hline
\end{tabular}


\index{joinRules@\te{joinRules} (\te{Vector} function)}
\index[function]{Vector!joinRules}

\begin{tabular}{|p{.8 in}|p{4.8 in}|}
\hline
&\\ \te{joinRules} &Join a number of rules together.\te{joinRules} is used for static elaboration only, no hardware is generated.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Rules joinRules (Vector#(vsize,Rules) vrules);
\end{libverbatim}
\\
\hline
\end{tabular}



{\bf Example - Folds}

Use fold to find the sum of the elements in a vector.
\begin{libverbatim}
     // my_vector1 is a vector of five integers {1,2,3,4,5}
     // \+ is a function which returns the sum of the elements
     // make sure you leave a space after the \+ and before the ,
          
     // This will build an adder tree, instantiating 4 adders, with a maximum
     // depth or delay of 3.  If foldr1 or foldl1 were used, it would
     // still instantiate 4 adders, but the delay would be 4.

     my_sum =  fold (\+ , my_vector1));
     // my_sum = 15
\end{libverbatim}

Use fold to find the element with the maximum value.
\begin{libverbatim}
     // my_vector1 is a vector of five integers  {2,45,5,8,32}

     my_max = fold (max, my_vector1);
     // my_max = 45 
\end{libverbatim}

Create a new vector using \te{mapPairs}.  The function \te{sum} is applied
to each pair of elements (the first and second, the third and fourth,
etc.).  If there is an uneven number of elements, the function \te{pass} is
applied to the remaining element.
\begin{libverbatim}
     // sum is defined as c = a+b
     function Int#(4) sum (Int #(4) a,Int #(4) b);
          Int#(4) c = a + b;
          return(c);
     endfunction

     // pass is defined as a
     function Int#(4) pass (Int #(4) a);
          return(a);
     endfunction

     // my_vector1 has the elements {0,1,2,3,4}

     my_vector2 = mapPairs(sum,pass,my_vector1);    
     // my_vector2 has the elements {1,5,4}
     // my_vector2[0] = 0 + 1
     // my_vector2[1] = 2 + 3
     // my_vector2[2] = 4   
\end{libverbatim}

%-----------------------------------------------------------------

\subsubsection{Scan Functions}

The \te{scan} family of functions applies a function over a vector,
creating a new vector result.  The \te{scan} function is similar to
\te{fold},  but the intermediate results are saved and returned in a
vector, instead of returning just the last result.  
The result of a \te{scan} function is a vector.
That is, given a 
vector of {\tt element\_type}, $V_0, V_1, ..., V_{n-1}$, an initial
value {\tt initb}  of
type {\tt b\_type}, and a function {\tt func}, application of the
{\tt scanr} functions creates a new vector $W$, where 
\begin{eqnarray*}
W_n     & = & init ; \\
W_{n-1} & = & func( V_{n-1}, W_n ) ; \\
W_{n-2} & = & func( V_{n-2}, W_{n-1} ) ; \\
...     &   & \\
W_1     & = & func( V_{1}, W_{2} ) ; \\
W_0     & = & func( V_0, W_1 ) ; \\
\end{eqnarray*}

\index{scanr@\te{scanr} (\te{Vector} function)}
\index[function]{Vector!scanr}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{scanr}&Apply a function over a vector, creating a new vector
result. Processes elements from  the
highest index position 
to the lowest, and fill the resulting vector in the same
way.  The result vector is 1 element longer than the input vector.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize1,b_type) 
         scanr(function b_type func(a_type x1, b_type x2), 
               b_type initb, 
               Vector#(vsize,a_type) vect)
  provisos (Add#(1, vsize, vsize1));
\end{libverbatim}
\\
\hline
\end{tabular}



\index{sscanr@\te{sscanr} (\te{Vector} function)}
\index[function]{Vector!sscanr}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{sscanr}&Apply a function over a vector, creating a new vector
result. The elements are processed from the highest index position to
the lowest.  The  $W_n$ element is dropped from the
result. Input and output vectors are the same size.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,b_type) 
         sscanr(function b_type func(a_type x1, b_type x2), 
                b_type initb, 
                Vector#(vsize,a_type) vect );
\end{libverbatim}
\\
\hline
\end{tabular}


The {\tt scanl} function creates the resulting vector in a
similar way as {\tt scanr} except that the processing happens
from the zeroth element up to the $n^{th}$ element.  
\begin{eqnarray*}
W_0 & = & init ; \\
W_1 & = &  func( W_0, V_0 ) ; \\
W_2 & = &  func( W_1, V_1 ) ; \\
... &   &  \\
W_{n-1} & = & func( W_{n-2}, V_{n-2} ) ; \\
W_n     & = & func( W_{n-1}, V_{n-1} ) ; \\
\end{eqnarray*}
The {\tt sscanl} function drops the first result, $init$, shifting
the result index by one. 

\index{scanl@\te{scanl} (\te{Vector} function)}
\index[function]{Vector!scanl}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{scanl}&Apply a function over a vector, creating a new vector
result. Processes elements from the zeroth element up to the
$n^{th}$ element.  The result vector is 1 element longer than the input vector.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize1,a_type) 
         scanl(function a_type func(a_type x1, b_type x2), 
               a_type q, 
               Vector#(vsize, b_type) vect)
  provisos (Add#(1, vsize, vsize1));
\end{libverbatim}
\\
\hline
\end{tabular}


\index{sscanl@\te{sscanl} (\te{Vector} function)}
\index[function]{Vector!sscanl}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
& \\ \te{sscanl}&Apply a function over a vector, creating a new vector
result. Processes elements from the zeroth element up to the
$n^{th}$ element.  The first result, $init$, is dropped, shifting the
result index up  
by one.  Input and output vectors are the same size.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize,a_type) 
         sscanl(function a_type func(a_type x1, b_type x2), 
                a_type q, 
                Vector#(vsize, b_type) vect );
\end{libverbatim}
\\
\hline
\end{tabular}

\index{mapAccumL@\te{mapAccumL} (\te{Vector} function)}
\index[function]{Vector!mapAccumL}

\begin{tabular}{|p{.8 in}|p{4.8 in}|}
\hline
&\\ \te{mapAccumL}&Map a function, but pass an accumulator from head to tail.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Tuple2 #(a_type, Vector#(vsize,c_type)) 
         mapAccumL (function Tuple2 #(a_type, c_type) 
                    func(a_type x, b_type y), a_type x0, 
                    Vector#(vsize,b_type) vect );
\end{libverbatim}
\\
\hline
\end{tabular}


\index{mapAccumR@\te{mapAccumR} (\te{Vector} function)}
\index[function]{Vector!mapAccumR}
\begin{tabular}{|p{.8 in}|p{4.8 in}|}
\hline
&\\ \te{mapAccumR}&Map a function, but pass an accumulator from tail to head.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Tuple2 #(a_type, Vector#(vsize,c_type)) 
         mapAccumR(function Tuple2 #(a_type, c_type) 
                   func(a_type x, b_type y), a_type x0, 
                    Vector#(vsize,b_type) vect );
\end{libverbatim}
\\
\hline
\end{tabular}




{\bf Examples - Scan}

Create a vector of factorials.
\begin{libverbatim}
     // \* is a function which returns the result of a multiplied by  b
     function Bit #(16) \* (Bit #(16) b, Bit #(8) a);
        return (extend (a) * b);
     endfunction
      
     // Create a vector of factorials by multiplying each input list element 
     // by the previous product (the output list element), to generate
     // the next product.  The seed is a Bit#(16) with a value of 1.
     // The elements are processed from the zeroth element up to the $n^{th}$ element.
           
     // my_vector1 = {1,2,3,4,5,6,7}
     Vector#(8,Bit #(16)) my_vector2 = scanl (\*, 16'd1, my_vector1);
     // 7 multipliers are generated

     // my_vector2 = {1,1,2,6,24,120,720,5040}
     // foldr with the same arguments would return just 5040.
\end{libverbatim}




% -------------------------------------------------------------------

  
\subsubsection{Monadic Operations}
  
Within Bluespec, there are some functions which can only be
invoked in certain contexts.  Two common examples are:
\te{ActionValue}, and module instantiation.  ActionValues can only be
invoked within an \te{Action} context, such as a rule block or an Action
method, and can be considered as two parts - the action and the value.
 Module instantiation can similarly be considered, modules can
only be instantiated in the module context, while the two parts
are the module instantiation (the action performed) and the interface (the
result returned).  These situations are considered \emph{monadic}.

  
When a monadic function is to be applied over a vector using
 map-like functions such
as {\tt map, zipWith}, or {\tt replicate}, the monadic versions
of these functions must be used.  Moreover, the context requirements of the
applied function must hold. The common application  for these functions
is in the generation (or instantiation) of vectors of hardware
components.  


\index{mapM@\te{mapM} (\te{Monad} function on {\te{Vector}})}
\index[function]{Vector!mapM}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{mapM}&Takes a monadic function and a vector, and
applies the function to all vector elements returning the vector of
corresponding results.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function m#(Vector#(vsize, b_type))
         mapM ( function m#(b_type) func(a_type x), 
                 Vector#(vsize, a_type) vecta )
   provisos (Monad#(m));
\end{libverbatim}
\\
\hline
\end{tabular}


\index{mapM\US@\te{mapM\US} (\te{Vector} function)}
\index[function]{Vector!mapM\US}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{mapM\_}&Takes a monadic function and a vector, applies the
function to all vector elements, and throws away the resulting vector leaving the action in its context.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function m#(void) mapM_(function m#(b_type) func(a_type x), 
                        Vector#(vsize, a_type) vect)
  provisos (Monad#(m));
\end{libverbatim}
\\
\hline
\end{tabular}


\index{zipWithM@\te{zipWithM} (\te{Vector} function)}
\index[function]{Vector!zipWithM}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{zipWithM} &Take a monadic function (which takes two arguments) and two vectors;
the function applied to the corresponding element from
each vector would return an action and result.
Perform all those actions and return the vector of corresponding results.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function m#(Vector#(vsize, c_type))
         zipWithM( function m#(c_type) func(a_type x, b_type y), 
                   Vector#(vsize, a_type) vecta, 
                   Vector#(vsize, b_type) vectb )
  provisos (Monad#(m));
\end{libverbatim}
\\
\hline
\end{tabular}


%\index{zipWithM\US@\te{zipWithM\US} (\te{Vector} function)}
%\index[function]{Vector!zipWithM\US}

\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{zipWithM\_} &Take a monadic function (which takes two
arguments) and two vectors; the function is applied to the corresponding
element from each vector.  This is the same as \te{zipWithM} but the
resulting vector is thrown away leaving the action in  its context.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function m#(void)
         zipWithM_(function m#(c_type) func(a_type x, b_type y), 
                   Vector#(vsize, a_type) vecta, 
                   Vector#(vsize, b_type) vectb )
  provisos (Monad#(m));
\end{libverbatim}
\\
\hline
\end{tabular}

\index{zipWith3M@\te{zipWith3M} (\te{Vector} function)}
\index[function]{Vector!zipWith3M}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{zipWith3M} & Same as \te{zipWithM} but combines three vectors
with a function. The function is applied to the corresponding element from
each vector and returns an action and the vector of corresponding results.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function m#(Vector#(vsize, c_type)) 
     zipWith3M( function m#(d_type) 
                func(a_type x, b_type y, c_type z),
                Vector#(vsize, a_type) vecta, 
                Vector#(vsize, b_type) vectb, 
                Vector#(vsize, c_type) vectc )
  provisos (Monad#(m));
\end{libverbatim}
\\
\hline
\end{tabular}

\index{genWithM@\te{genWithM} (\te{Vector} function)}
\index[function]{Vector!genWithM}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{genWithM} & Generate a vector of elements  by applying the
given monadic function to 0 through n-1.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function m#(Vector#(vsize, element_type)) 
         genWithM(function m#(element_type) func(Integer x))
  provisos (Monad#(m));
\end{libverbatim}
\\
\hline
\end{tabular}


\index{replicateM@\te{replicateM} (\te{Vector} function)}
\index[function]{Vector!replicateM}
\begin{tabular}{|p{.7 in}|p{4.9 in}|}
\hline
&\\ \te{replicateM} & Generate a vector of elements  by using
the given monadic value repeatedly.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function m#(Vector#(vsize, element_type)) 
         replicateM( m#(element_type) c)
  provisos (Monad#(m));
\end{libverbatim}
\\
\hline
\end{tabular}

{\bf Examples - Creating a Vector of Registers}

The following example shows some common uses of the {\te{Vector}}
type. We first create a vector of registers, and show how to
populate this vector.   We then continue with some examples of
accessing and updating the registers within the vector, as
well as alternate ways to do the same. 

\begin{libverbatim}
   // First define a variable to hold the register interfaces. 
   // Notice the variable is really a vector of Interfaces of type Reg,
   // not a vector of modules.
   Vector#(10,Reg#(DataT))   vectRegs ;

   // Now we want to populate the vector, by filling it with Reg type
   // interfaces, via the mkReg module.
   // Notice that the replicateM function is used instead of the
   // replicate function since mkReg function is creating a module.
   vectRegs <- replicateM( mkReg( 0 ) ) ;

   // ...

   // A rule showing a read and write of one register within the
   // vector.
   // The readReg function is required since the selection of an
   // element from vectRegs returns a Reg#(DType) interface, not the
   // value of the register.  The readReg functions converts from a
   // Reg#(DataT) type to a DataT type. 
   rule zerothElement ( readReg( vectRegs[0] ) > 20 ) ;
      // set 0 element to 0
      // The parentheses are required in this context to give
      // precedence to the selection over the write operation.
      (vectRegs[0]) <= 0 ;
      
      // Set the 1st element to 5
      // An alternate syntax 
      vectRegs[1]._write( 5 ) ;
   endrule

   rule lastElement ( readReg( vectRegs[9] ) > 200 ) ;
      // Set the 9th element to -10000
      (vectRegs[9]) <= -10000 ;
   endrule
   
   // These rules defined above can execute simultaneously, since
   // they touch independent registers

   // Here is an example of dynamic selection,  first we define a
   // register to be used as the selector. 
   Reg#(UInt#(4))  selector <- mkReg(0) ;

   // Now define another Reg variable which is selected from the
   // vectReg variable.  Note that no register is created here, just
   // an alias is defined.
   Reg#(DataT)  thisReg = select(vectRegs, selector ) ;
   
   //The above statement is equivalent to:
   //Reg#(DataT) thisReg = vectRegs[selector] ;


   // If the selected register is greater than 20'h7_0000, then its
   // value is reset to zero.  Note that the vector update function is
   // not required since we are changing the contents of a register
   // not the vector vectReg.
   rule reduceReg( thisReg > 20'h7_0000 ) ;
      thisReg <= 0 ;
      selector <= ( selector < 9 ) ? selector + 1 : 0 ;
   endrule

   // As an alternative, we can define N rules which each check the
   // value of one register and update accordingly.  This is done by
   // generating each rule inside an elaboration-time for-loop.
   
   Integer i;  // a compile time variable 
   for ( i = 0 ; i < 10 ; i = i + 1 ) begin
      rule checkValue( readReg( vectRegs[i] ) > 20'h7_0000 ) ;
         (vectRegs[i]) <= 0 ;
      endrule
   end
\end{libverbatim}



% the following 3 functions have been removed from the printed
% documentation.

% \index{foldlM@\te{foldlM} (\te{Vector} function)}
% \begin{tabular}{|p{.7 in}|p{4.9 in}|}
% \hline
% &\\ \te{foldlM} & \\
% & \\ \cline{2-2}
% &\begin{libverbatim}
% function m#(b_type) foldlM 
%                     (function m#(b_type) func(b_type y, a_type x), 
%                      b_type initb, 
%                      Vector#(vsize,a_type) vect )
%   provisos (Monad#(m));
% \end{libverbatim}
% \\
% \hline
% \end{tabular}

% \index{foldM@\te{foldM} (\te{Vector} function)}

% \begin{tabular}{|p{.7 in}|p{4.9 in}|}
% \hline
% &\\ \te{foldM} & Vector has at least 1 element.\\
% & \\ \cline{2-2}
% &\begin{libverbatim}
% function m#(a_type) foldM (
%                    function m#(a_type) func(a_type y, a_type x), 
%                 Vector#(vsize,a_type) vecta )
%   provisos (Monad#(m), Add#(1, xxx, vsize)); 
% \end{libverbatim}
% \\
% \hline
% \end{tabular}
  

% \index{foldrM@\te{foldrM} (\te{Vector} function)}
% \begin{tabular}{|p{.7 in}|p{4.9 in}|}
% \hline
% &\\ \te{foldrM}& \\
% & \\ \cline{2-2}
% &\begin{libverbatim}
% function m#(b_type) foldrM (
%             function m#(b_type) func(a_type x, b_type y), 
%             b_type e, 
%             Vector#(vsize,a_type) vecta )
%   provisos (Monad#(m));
% \end{libverbatim}
% \\
% \hline
% \hline
% \end{tabular}

% ----------------------------------------------------------------


%----------------------------------------------------------------

\subsubsection{Converting to and from Vectors}
 
There are functions which convert between Vectors and other types.
\index{toList@\te{toList} (\te{Vector} function)}
\index[function]{Vector!toList}

\begin{tabular}{|p{.9 in}|p{4.7 in}|}
\hline
&\\ \te{toList} & Convert a Vector to a List.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function List#(element_type) 
         toList (Vector#(vsize, element_type) vect);
\end{libverbatim}
\\
\hline
\end{tabular}

\index{toVector@\te{toVector} (\te{Vector} function)}
\index[function]{Vector}

\begin{tabular}{|p{.9 in}|p{4.7 in}|}
\hline
&\\ \te{toVector}&Convert a List to a Vector.\\ 
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize, element_type) 
         toVector ( List#(element_type) lst);
\end{libverbatim}
\\
\hline
\end{tabular}


\index{arrayToVector@\te{arrayToVector} (\te{Vector} function)}
\index[function]{Vector!arrayToVector}
\begin{tabular}{|p{.9 in}|p{4.7 in}|}
\hline
&\\ \te{arrayToVector}&Convert an array to a Vector.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function Vector#(vsize, element_type) 
         arrayToVector ( element_type[ ] arr);
\end{libverbatim}
\\
\hline
\end{tabular}


\index{vectorToArray@\te{vectorToArray} (\te{Vector} function)}
\index[function]{Vector!vectorToArray}
\begin{tabular}{|p{.9 in}|p{4.7 in}|}
\hline
&\\ \te{vectorToArray}&Convert a Vector to an array.\\
& \\ \cline{2-2}
&\begin{libverbatim}
function element_type[ ] 
     vectorToArray (Vector#(vsize, element_type) vect);
\end{libverbatim}
\\
\hline
\end{tabular}

\index{toChunks@\te{toChunks} (\te{Vector} function)}
\index[function]{Vector!toChunks}
\begin{tabular}{|p{.9 in}|p{4.7 in}|}
\hline
&\\ \te{toChunks}&Convert a value to a Vector of chunks, possibly
padding the final chunk.  The input type and size as well as the chunk
type and size  are determined from their types. \\
 \cline{2-2}
&\begin{libverbatim}
function Vector#(n_chunk, chunk_type) toChunks(type_x x)
    provisos( Bits#(chunk_type, chunk_sz), Bits#(type_x, x_sz)
            , Div#(x_sz, chunk_sz, n_chunk) );
\end{libverbatim}
\\
\hline
\end{tabular}


{\bf Example - Converting to and from Vectors}

Convert the vector \te{my\_vector} to a list named \te{my\_list}.
\begin{libverbatim}
     Vector#(5,Int#(13)) my_vector;
     List#(Int#(13)) my_list = toList(my_vector);
\end{libverbatim}


\subsubsection{ListN}

\index{ListN@\te{ListN} (type)}

{\bf Package name}


\begin{verbatim}
import ListN :: * ;
\end{verbatim}

{\bf Description}

ListN is an alternative implementation of Vector which is
preferred for sequential list processing functions, such as head, tail, map,
fold, etc.  All Vector functions are available, by substituting
ListN for Vector.  See the Vector documentation (\ref{lib-vector})
for details.  If the implementation requires random access to
items in the list, the Vector construct is recommended.  Using
ListN where Vectors is recommended (and visa-versa) can lead to
very long static elaboration times. 

The {\te{ListN}}  package defines an abstract data type which is
a ListN of a specific length.  Functions which create and operate
on this type are also defined within this package.
Because it is abstract, there are no constructors available for this type
(like {\te{Cons}} and {\te{Nil}} for the {\te{List}} type).
\BBS
 struct ListN\#(vsize,a\_type) 
       {\rm{\emph{$\cdots$ abstract $\cdots$}}}
\EBS
Here, the type variable {\qbs{a\_type}} represents the type of the
contents of the listN 
while type variable {\qbs{vsize}} represents the length of the
ListN.
